package com.leetcode.lccup;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/4/16 15:08
 */
public class LCCUP2烹饪料理 {

    private static int[] materials;
    private static int[][] cookbooks, attribute;
    private static int n, m, limit, ans = -1;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        int n = Integer.parseInt(ss[0]), m = Integer.parseInt(ss[1]), limit = Integer.parseInt(ss[2]);
        int[] materials = new int[n];
        int[][] cookbooks = new int[m][n], attribute = new int[m][2];
        ss = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) materials[i] = Integer.parseInt(ss[i]);
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            for (int j = 0; j < n; j++) cookbooks[i][j] = Integer.parseInt(ss[j]);
        }
        for (int i = 0; i < m; i++) {
            ss = reader.readLine().split(" ");
            attribute[i] = new int[]{Integer.parseInt(ss[0]), Integer.parseInt(ss[1])};
        }
        writer.write(perfectMenu(materials, cookbooks, attribute, limit) + "\n");
        writer.flush();
    }

    public static int perfectMenu(int[] _materials, int[][] _cookbooks, int[][] _attribute, int _limit) {
        n = _materials.length;
        m = _cookbooks.length;
        materials = _materials;
        cookbooks = _cookbooks;
        attribute = _attribute;
        limit = _limit;
        dfs(0, 0, 0);
        return ans;
    }

    private static void dfs(int start, int sum1, int sum2) {
        if (sum2 >= limit) ans = Math.max(ans, sum1);
        //枚举制作每一道料理
        for (int i = start; i < m; i++) {
            int[] cookbook = cookbooks[i];
            if (check(cookbook)) {
                //制作当前料理
                for (int j = 0; j < cookbook.length; j++) materials[j] -= cookbook[j];
                dfs(i + 1, sum1 + attribute[i][0], sum2 + attribute[i][1]);
                //还原现场
                for (int j = 0; j < cookbook.length; j++) materials[j] += cookbook[j];
            }
        }
    }

    private static boolean check(int[] cookbook) {
        //检查当前剩余材料是否充足
        for (int i = 0; i < cookbook.length; i++) {
            if (materials[i] < cookbook[i]) return false;
        }
        return true;
    }
}
